package com.explorati.LeetCode017.letterCombinations;

import java.util.*;

/**
 * @ Author : Weijian_Wang
 * @ Date : Created in 22:18 2020/9/22 0022
 * @ Description ：回溯算法第一练
 */
public class Solution {

    /**
     * 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
     * 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
     * @param digits
     * @return
     */

     private static final String[] map = {
             " ",           //0
             "",            //1
             "abc",         //2
             "def",         //3
             "ghi",         //4
             "jkl",         //5
             "mno",         //6
             "pqrs",        //7
             "tuv",         //8
             "wxyz"};       //9

    List<String> res = new ArrayList<String>();
    public List<String> letterCombinations(String digits) {
        if(digits == null) {
            return res;
        }

        findCombinations(digits, 0, "");
        return res;
    }

    /**
     * 寻找和digits[index]匹配的字母，获得digits[0...index]翻译得到的解
     * @param digits   传入的字符串，如"23"
     * @param index    当前处理的字符位置，如'2':0, '3': 1
     * @param preStr   保存了此时从digits[0...index-1]翻译得到的一个字母字符串
     */
    private void findCombinations(String digits, int index, String preStr) {
        if(index == digits.length()) {
            res.add(preStr);
            return ;
        }
        //当前位置的字符
        char c = digits.charAt(index);
        //当前位置对应字符的对应的字符串，如 2-->"abc"
        String letters = map[c - '0'];

        for(int i = 0; i < letters.length(); i++) {
            findCombinations(digits, index + 1, preStr + letters.charAt(i));
        }
    }

}
